package tree

import "fmt"

type BinaryTree struct {
	root *Node
}

func NewBinaryTree(rootVal interface{}) *BinaryTree {
	return &BinaryTree{NewNode(rootVal)}
}

// 中序遍历
func (that *BinaryTree) InOrderTraverse() {
	p := that.root
	// 通过栈来实现递归访问
	s := NewArrayStack()

	for !s.IsEmpty() || p != nil {
		if p != nil {
			// 将当前节点压入栈
			s.Push(p)
			// 遍历左子节点
			p = p.left
		} else {
			// s不为空
			// 返回访问当前节点
			tmp := s.Pop().(*Node)
			fmt.Printf("%+v \n", tmp.data)
			// 然后遍历右子节点
			p = tmp.right
		}
	}
}

// 先序遍历
func (that *BinaryTree) PreOrderTraverse() {
	p := that.root
	s := NewArrayStack()

	for !s.IsEmpty() || p != nil {
		if p != nil {
			// 访问当前节点
			fmt.Printf("%+v \n", p.data)
			// 将当前节点压入栈中（压入栈的必须是当前节点,否则访问完右子节点后无法原路返回）
			s.Push(p)
			// 访问左子节点
			p = p.left
		} else {
			// s不为空，访问右子节点
			p = s.Pop().(*Node).right
		}
	}
}

// 后序遍历
func (that *BinaryTree) PostOrderTraverse() {
	// 借助两个栈来遍历
	s1 := NewArrayStack()
	s2 := NewArrayStack()
	// 将根节点压入s1栈
	s1.Push(that.root)

	for !s1.IsEmpty() {
		p := s1.Pop().(*Node)
		// 将当前节点压入s2栈
		s2.Push(p)
		// 遍历左子节点
		// 将当前节点的左子节点压入s1栈
		if p.left != nil {
			s1.Push(p.left)
		}
		// 将当前节点的右子节点压入s1栈
		if p.right != nil {
			s1.Push(p.right)
		}
	}

	for !s2.IsEmpty() {
		// 从s2中取出栈顶元素
		node := s2.Pop().(*Node)
		fmt.Printf("%+v \n", node.data)
	}
}
